package day_2022_4_to_7.nowcoder;

import java.util.ArrayList;

/**
 * 二叉树中和为某一值的路径(二)
 * @author haomin
 * @date 2022/05/05 18:36
 **/
public class FindPath_21f {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        // 结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        // 待选集
        ArrayList<Integer> list = new ArrayList<Integer>();

        FindPathHelper(root,result,list,expectNumber);
        return result;
    }
    private void FindPathHelper(TreeNode root,ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int expectNumber) {
        // 当前节点为空说明当前路径已经走到叶子结点，已走完，return
        if (root == null) {
            return;
        }
        // 每次遇到新节点，将expectNumber减去该root.val，当expectNumber减到0时，该路径就是所求路径
        expectNumber -= root.val;

        // 1.先在待选集中添加一个值（当前root节点）
        list.add(root.val);

        // 2.判断是否满足条件（该路径的节点值和为expectNumber）
        if (root.left == null && root.right == null && expectNumber == 0) {
            // 如果满足，则将当前待选集合list 添加到结果集result 中
            // 进行深拷贝
            result.add(new ArrayList<Integer>(list));
        }

        // 3.DFS（继续添加左右子树的节点到待选集中）
        FindPathHelper(root.left, result, list, expectNumber);
        FindPathHelper(root.right, result, list, expectNumber);

        // 4.回退（每判断一条路径list后，将当前路径list中最后一个节点删除，返回上一层，判断其上一层右子树路径是否满足条件）
        list.remove(list.size()-1);
    }
}